package com.clstu.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 79子集
 */
class Solution6 {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(subsets(nums));
    }


    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //先判断是否数组空
        if(nums.length == 0){
            return res;
        }
        //回溯之后返回结果即可
        //用动态数组来生成结果
        List<Integer> path = new ArrayList<>();
        dfs(nums,0,res,path);
        return res;
    }

    //编写方法实现递归回溯,第index个数要或不要
    public static void dfs(int[] nums,int index,List<List<Integer>> res,List<Integer> path){
        //如果到底,说明有一种子集了,加入返回
        if(index == nums.length){
            res.add(new ArrayList<>(path));
            return ;
        }
        //分两种情况,当前index下标的数要或者不要
        //不要当前数
        dfs(nums,index+1,res,path);
        //要当前数
        path.add(nums[index]);
        dfs(nums,index+1,res,path);
        //动态数组加入元素之后需要即时清除,执行完毕之后path一定是空的才行
        path.remove(path.size()-1);
    }
}
